SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Visvalingam–Whyatt algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Visvalingam–Whyatt algorithm</span></span>

</h1>

</header>

<p>The <b>Visvalingam–Whyatt algorithm</b>, or simply the <b>Visvalingam algorithm</b>, is an algorithm that <a href="Decimation_(signal_processing)" class="mw-redirect" title="Decimation (signal processing)">decimates</a> a curve composed of line segments to a similar curve with fewer points, primarily for usage in <a href="Cartographic_generalisation" class="mw-redirect" title="Cartographic generalisation">cartographic generalisation</a>.

</p>

<p>Given a <a href="Polygonal_chain" title="Polygonal chain">polygonal chain</a> (often called a polyline), the algorithm attempts to find a similar chain composed of fewer points.

</p><p>Points are assigned an importance based on local conditions, and points are removed from the least important to most important.

</p><p>In Visvalingam's algorithm, the importance is related to the triangular area added by each point.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>Given a chain of <a href="Two-dimensional_space" title="Two-dimensional space">2d</a> points <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}}">

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}}</annotation>

</semantics>

</math></span><img src="./607f276bd489403cfdfb62b32f21b6ccb4241a5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.214ex; height:6.176ex;" alt="{\displaystyle \left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}}" loading="lazy"></span>, the importance of each interior point is computed by finding the area of the triangle formed by it and its immediate neighbors. This can be done quickly using a matrix <a href="Determinant" title="Determinant">determinant</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Alternatively, the equivalent formula below can be used<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i}={\frac {1}{2}}\left|x_{i-1}y_{i}+x_{i}y_{i+1}+x_{i+1}y_{i-1}-x_{i-1}y_{i+1}-x_{i}y_{i-1}-x_{i+1}y_{i}\right|}</annotation>

</semantics>

</math></span><img src="./6688b68e324d272a933cec1de8f2a1df0df46a86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:64.736ex; height:5.176ex;" alt="{\displaystyle A_{i}={\frac {1}{2}}\left|x_{i-1}y_{i}+x_{i}y_{i+1}+x_{i+1}y_{i-1}-x_{i-1}y_{i+1}-x_{i}y_{i-1}-x_{i+1}y_{i}\right|}" loading="lazy"></span></dd></dl>

<p>The minimum importance point <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}}</annotation>

</semantics>

</math></span><img src="./5bab39399bf5424f25d957cdc57c84a0622626d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.059ex; height:2.009ex;" alt="{\displaystyle p_{i}}" loading="lazy"></span> is located and marked for removal (note that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i-1}}</annotation>

</semantics>

</math></span><img src="./2d4c73b6def8ec1c916e937d5106018f1dc2edde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.643ex; height:2.509ex;" alt="{\displaystyle A_{i-1}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i+1}}</annotation>

</semantics>

</math></span><img src="./4ec7d4b1415b77c7352d4212755acfbc8e1bb1ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.643ex; height:2.509ex;" alt="{\displaystyle A_{i+1}}" loading="lazy"></span> will need to be recomputed). This process is repeated until either the desired number of points is reached, or the contribution of the least important point is large enough to not neglect.

</p>

<div class="mw-heading mw-heading3"><h3 id="Advantages">Advantages</h3></div>

<ul><li>The algorithm is easy to understand and explain, but is often competitive with much more complex approaches.</li>

<li>With the use of a <a href="Priority_queue" title="Priority queue">priority queue</a>, the algorithm is performant on large inputs, since the importance of each point can be computed using only its neighbors, and removing a point only requires recomputing the importance of two other points.</li>

<li>It is simple to generalize to higher dimensions, since the area of the triangle between points has a consistent meaning.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Disadvantages">Disadvantages</h3></div>

<ul><li>The algorithm does not differentiate between sharp spikes and shallow features, meaning that it will clean up sharp spikes that may be important.</li>

<li>The algorithm simplifies the entire length of the curve evenly, meaning that curves with high and low detail areas will likely have their fine details eroded.</li></ul>

<ul><li><a href="Curve_fitting" title="Curve fitting">Curve fitting</a></li></ul>

<p>Alternative algorithms for line simplification include:

</p>

<ul><li><a href="Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm" title="Ramer–Douglas–Peucker algorithm">Ramer–Douglas–Peucker</a></li>

<li>Reumann–Witkam</li>

<li>Opheim simplification</li>

<li>Lang simplification</li>

<li>Zhao–Saalfeld algorithm</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<dl><dt>Notes</dt></dl>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://people.richland.edu/james/lecture/m116/matrices/applications.html#:~:text=The%20legs%20of%20the%20three,/%202%20=%209/2.">"6.5 – Applications of Matrices and Determinants"</a>. <i>people.richland.edu</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-07-07</span></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://people.richland.edu/james/lecture/m116/matrices/area.html">"Untitled Document"</a>. <i>people.richland.edu</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-07-07</span></span>.</cite></span>

</li>

</ol></div></div>

<dl><dt>Bibliography</dt></dl>

<ul><li><cite id="CITEREFVisvalingamWhyatt1993" class="citation journal cs1">Visvalingam, M.; Whyatt, J. D. (1993). <a rel="nofollow" class="external text" href="https://hull-repository.worktribe.com/preview/376364/000870493786962263.pdf">"Line generalisation by repeated elimination of points"</a> <span class="cs1-format">(PDF)</span>. <i>The Cartographic Journal</i>. <b>30</b> (1): <span class="nowrap">46–</span>51. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1179%2F000870493786962263">10.1179/000870493786962263</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0008-7041">0008-7041</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.jasondavies.com/simplify/">Interactive example of the algorithm</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-05-31" href="https://en.wikipedia.org/wiki/?title=Visvalingam%E2%80%93Whyatt_algorithm&oldid=1226567815">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>